package main.java.indi.zyj.hot100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;




//for 选择 in 选择列表:
//        # 做选择
//        将该选择从选择列表移除
//        路径.add(选择)
//        backtrack(路径, 选择列表)
//        # 撤销选择
//        路径.remove(选择)
//        将该选择再加入选择列表
public class _47_permute {

    List<List<Integer>> res = null;
    LinkedList<Integer> path = null;
    boolean[] used = null;

    public List<List<Integer>> permute(int[] nums) {

        if (nums == null || nums.length == 0) {
            return res;
        }

        res = new ArrayList<>();
        path = new LinkedList<>();
        used = new boolean[nums.length];

        backtrack(nums);

        return res;
    }

    private void backtrack(int[] nums) {
        if (nums.length == path.size()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.addLast(nums[i]);
            backtrack(nums);
            path.removeLast();
            used[i] = false;
        }
    }


}
